package com.beijing.demo.find;

import java.util.Arrays;

/**
 * 曹旭
 * 2025/4/23
 * 二分查找:
 * 找出有序数组中,小于等于num最右的位置
 * 人话:
 * 找出有序数组中,小于等于num的最大值,返回其坐标.
 */
public class FindRightNumber {
    public static void main(String[] args) {
        System.out.println("test start~~");
        int testTimes = 1000000;
        int len = 100;
        int value = 200;
        for (int i = 0; i < testTimes; i++) {
            int[] arrs = ArrayUtils.getRanArray(len,value);
            int num = ArrayUtils.getRanValue(value);
            Arrays.sort(arrs);
            if(getRightNum(arrs,num) != binaryFindNum(arrs,num)){
                System.out.println("fucking fuck~~");
                break;
            }
        }
        System.out.println("test end~~");
    }

    /**
     * 暴力解法
     * @param arrs
     * @param num
     * @return
     */
    public static int getRightNum(int[] arrs,int num){
        int resultInd = -1;
        if(arrs == null || arrs.length == 0){
            return resultInd;
        }
        for (int i = 0; i < arrs.length; i++) {
            if(arrs[i] <= num){
               resultInd = i;
            }else {
                break;
            }
        }
        return resultInd;
    }


    /**
     * 二分解法,找出小于等于num的最大值的下标
     * @return
     */
    public static int binaryFindNum(int[] arrs,int num){
        int resultInd = -1;
        if(arrs == null || arrs.length == 0){
            return resultInd;
        }
        int l = 0,r = arrs.length - 1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(arrs[mid] > num){
                r = mid -1;
            }else {
                resultInd = mid;
                l = mid +1;
            }
        }
        return resultInd;
    }
}
